#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define s(t) scanf("%d", &t)
#define sl(t) scanf("%lld", &t)
#define MAXN 505
#define MAXM 100005
using namespace std;
typedef long long ll;
int b[] = {2,3,5,7,11,13,17,19,23,29,31};
ll mulmod(ll a, ll b, ll c){
    ll x = 0, y = a%c;
    while (b > 0){
        if (b & 1){
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

int modulo(int a, int b, int c){
    ll x = 1, y = a;
    while (b > 0){
        if (b & 1){
            x = mulmod(x,y,c);
        }
        y = mulmod(y,y,c);
        b /= 2;
    }
    return x%c;
}

bool miller(ll p, int iter){
    if (p < 2) return false;
    if (p!=2 && !(p&1)) return false;
    for (int i=0;i<10;i++){
        if (p == b[i]) return true;
        else if (p%b[i]==0) return false;
    }
    ll s = p - 1;
    while (!(s & 1)){
        s >>= 1;
    }
    ll mod;
    for (int i=0;i<iter;i++){
        ll a = rand() % (p-1)+1, temp = s;
        ll mod = modulo(a, temp, p);
        while (temp != p-1 && mod != 1 && mod != p-1){
            mod = mulmod(mod, mod, p);
            temp <<= 1;
        }
        if (mod != p-1 && temp % 2 == 0){
            return false;
        }
    }
    return true;
}

int main()
{
    freopen("WITMATH.txt","r", stdin);
    ll t,n;
    sl(t);
    while (t--){
        sl(n);
        while (!miller(n, 1)) n--;
        cout << n << endl;
    }
    return 0;
}
